#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int TDataType;
typedef struct Tree
{
	TDataType val;
	struct Tree* left;
	struct Tree* right;
}Tree;

Tree* BuyTree(TDataType x)
{
	Tree* t = (Tree*)malloc(sizeof(Tree));
	if (t == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	t->val = x; 
	t->left = NULL;
	t->right = NULL;

	return t;
}

bool IsSame(Tree* root, Tree* sub)
{
	if (!root && !sub)
		return true;

	if (!root || !sub)
		return false;

	if (root->val != sub->val)
		return false;

	return IsSame(root->left, sub->left) && IsSame(root->right, sub->right);
}

bool IsSubTree(Tree* root, Tree* sub)
{
	if (!root)
		return false;

	if (IsSame(root, sub))
		return true;

	return IsSubTree(root->left, sub) || IsSubTree(root->right, sub);
}


void test()
{
	Tree* t1 = BuyTree(1);
	Tree* t2 = BuyTree(2);
	Tree* t3 = BuyTree(3);
	Tree* t4 = BuyTree(4);
	Tree* t5 = BuyTree(5);

	t1->left = t2;
	t1->right = t3;
	t2->left = t4;
	t2->right = t5;

	Tree* n1 = BuyTree(2);
	Tree* n2 = BuyTree(4);
	Tree* n3 = BuyTree(5);
	n1->left = n2;
	n1->right = n3;

	if (IsSubTree(t1, n1))
		printf("true\n");
	else
		printf("false\n");
}

int main()
{
	test();
	return 0;
}